package com.lw.leetcode.tree.c;

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 480. 滑动窗口中位数
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/8 10:40
 */
public class MedianSlidingWindow {


    public static void main(String[] args) {
        MedianSlidingWindow test = new MedianSlidingWindow();

        // [1,-1,-1,3,5,6]
//        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
//        int k = 3;

        // [1,-1,-1,3,5,6]
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 2;

        double[] doubles = test.medianSlidingWindow(arr, k);
        System.out.println(Arrays.toString(doubles));
    }

    public double[] medianSlidingWindow(int[] nums, int k) {
        int[] arr = new int[k];
        System.arraycopy(nums, 0, arr, 0, k);
        Arrays.sort(arr);
        Node st = new Node(Integer.MIN_VALUE);
        Node end = new Node(Integer.MIN_VALUE);
        Node item = st;
        boolean flag = (k & 1) == 0;
        int t = (k - 1) >> 1;
        Node mid = null;
        TreeMap<Integer, Node> map = new TreeMap<>();
        for (int i = 0; i < k; i++) {
            Node node = new Node(arr[i]);
            item.next = node;
            node.pre = item;
            if (i == t) {
                mid = node;
            }
            map.put(arr[i], node);
            item = node;
        }
        item.next = end;
        end.pre = item;

        int l = nums.length - k;

        double[] values = new double[l + 1];
        values[0] = flag ? ((double) mid.val + mid.next.val) / 2 : mid.val;

        for (int i = 0; i < l; i++) {
            int b = nums[i];
            if (b >= mid.val) {
                mid = mid.pre;
            }
            Node node = map.get(b);
            if (node.pre.val == node.val) {
                map.put(b, node.pre);
            } else {
                map.remove(b);
            }
            Node pre = node.pre;
            Node next = node.next;
            pre.next = next;
            next.pre = pre;
            node.next = null;
            node.pre = null;

            int a = nums[i + k];
            Map.Entry<Integer, Node> entry = map.floorEntry(a);
            pre = st;
            if (entry != null) {
                pre = entry.getValue();
            }
            node = new Node(a);
            map.put(a, node);
            next = pre.next;
            pre.next = node;
            node.next = next;
            next.pre = node;
            node.pre = pre;
            if (a >= mid.val) {
                mid = mid.next;
            }
            values[i + 1] = flag ? ((double) mid.val + mid.next.val) / 2 : mid.val;
        }
        return values;
    }

    private static class Node {
        private int val;
        private Node next;
        private Node pre;

        private Node(int val) {
            this.val = val;
        }
    }

}
